{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find the Winner of the Circular Game"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #recursion #queue #array #math #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #递归 #队列 #数组 #数学 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findTheWinner"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找出游戏的获胜者"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>共有 <code>n</code> 名小伙伴一起做游戏。小伙伴们围成一圈，按 <strong>顺时针顺序</strong> 从 <code>1</code> 到 <code>n</code> 编号。确切地说，从第 <code>i</code> 名小伙伴顺时针移动一位会到达第 <code>(i+1)</code> 名小伙伴的位置，其中 <code>1 &lt;= i &lt; n</code> ，从第 <code>n</code> 名小伙伴顺时针移动一位会回到第 <code>1</code> 名小伙伴的位置。</p>\n",
    "\n",
    "<p>游戏遵循如下规则：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li>从第 <code>1</code> 名小伙伴所在位置 <strong>开始</strong> 。</li>\n",
    "\t<li>沿着顺时针方向数 <code>k</code> 名小伙伴，计数时需要 <strong>包含</strong> 起始时的那位小伙伴。逐个绕圈进行计数，一些小伙伴可能会被数过不止一次。</li>\n",
    "\t<li>你数到的最后一名小伙伴需要离开圈子，并视作输掉游戏。</li>\n",
    "\t<li>如果圈子中仍然有不止一名小伙伴，从刚刚输掉的小伙伴的 <strong>顺时针下一位</strong> 小伙伴 <strong>开始</strong>，回到步骤 <code>2</code> 继续执行。</li>\n",
    "\t<li>否则，圈子中最后一名小伙伴赢得游戏。</li>\n",
    "</ol>\n",
    "\n",
    "<p>给你参与游戏的小伙伴总数 <code>n</code> ，和一个整数 <code>k</code> ，返回游戏的获胜者。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/03/25/ic234-q2-ex11.png\" style=\"width: 500px; height: 345px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 5, k = 2\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>游戏运行步骤如下：\n",
    "1) 从小伙伴 1 开始。\n",
    "2) 顺时针数 2 名小伙伴，也就是小伙伴 1 和 2 。\n",
    "3) 小伙伴 2 离开圈子。下一次从小伙伴 3 开始。\n",
    "4) 顺时针数 2 名小伙伴，也就是小伙伴 3 和 4 。\n",
    "5) 小伙伴 4 离开圈子。下一次从小伙伴 5 开始。\n",
    "6) 顺时针数 2 名小伙伴，也就是小伙伴 5 和 1 。\n",
    "7) 小伙伴 1 离开圈子。下一次从小伙伴 3 开始。\n",
    "8) 顺时针数 2 名小伙伴，也就是小伙伴 3 和 5 。\n",
    "9) 小伙伴 5 离开圈子。只剩下小伙伴 3 。所以小伙伴 3 是游戏的获胜者。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 6, k = 5\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>小伙伴离开圈子的顺序：5、4、6、2、3 。小伙伴 1 是游戏的获胜者。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= k &lt;= n &lt;= 500</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>你能否使用线性时间复杂度和常数空间复杂度解决此问题？</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-the-winner-of-the-circular-game](https://leetcode.cn/problems/find-the-winner-of-the-circular-game/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-the-winner-of-the-circular-game](https://leetcode.cn/problems/find-the-winner-of-the-circular-game/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['5\\n2', '6\\n5']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheWinner(self, n: int, k: int) -> int:\n",
    "        def f1(A, start):\n",
    "            sz = len(A)\n",
    "            if sz == 1:\n",
    "                return A[start]\n",
    "            nstart = start + k - 1\n",
    "            nstart %= sz\n",
    "            A.pop(nstart)\n",
    "            return f1(A, nstart % (sz - 1))\n",
    "                \n",
    "            \n",
    "        A = [i + 1 for i in range(n)]\n",
    "        return f1(A, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheWinner(self, n: int, k: int) -> int:\n",
    "        res=0\n",
    "        for i in range(2,n+1):\n",
    "            res=(k+res)%i\n",
    "        return res+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheWinner(self, n: int, k: int) -> int:\n",
    "        que = deque(i+1 for i in range(n))\n",
    "        while len(que) != 1:\n",
    "            for _ in range(k-1):\n",
    "                temp = que.popleft()\n",
    "                que.append(temp)\n",
    "            que.popleft()\n",
    "        return que[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheWinner(self, n: int, k: int) -> int:\n",
    "        n = deque(range(1,n+1))\n",
    "        while len(n)>1:\n",
    "            for i in range(k-1):\n",
    "                n.append(n.popleft())\n",
    "            n.popleft()\n",
    "        return n[0]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None, prev=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "        self.prev = prev\n",
    "\n",
    "\n",
    "class LinkedList:\n",
    "    def __init__(self, head=None):\n",
    "        self.head = head\n",
    "        self.size = 1 if self.head else 0\n",
    "\n",
    "    def addNode(self, node):\n",
    "        if not self.head:\n",
    "            self.head = node\n",
    "            self.head.next, self.head.prev = self.head, self.head\n",
    "        else:\n",
    "            temp = self.head.prev\n",
    "            temp.next = self.head.prev = node\n",
    "            node.next, node.prev = self.head, temp\n",
    "        self.size += 1\n",
    "\n",
    "    def delNode(self, node):\n",
    "        if node == self.head:\n",
    "            self.head = self.head.next\n",
    "        nxt, pre = node.next, node.prev\n",
    "        node.next = node.prev = None\n",
    "        nxt.prev, pre.next = pre, nxt\n",
    "        self.size -= 1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findTheWinner(self, n: int, k: int) -> int:\n",
    "        ring = LinkedList()\n",
    "        for i in range(1, n+1):\n",
    "            ring.addNode(Node(i))\n",
    "        cur = ring.head\n",
    "        while ring.size > 1:\n",
    "            for i in range(k - 1):\n",
    "                cur = cur.next\n",
    "            temp = cur.next\n",
    "            ring.delNode(cur)\n",
    "            cur = temp\n",
    "        return ring.head.val  # 或者 cur.val 也行\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findTheWinner(self, n: int, k: int) -> int:\n",
    "        def helper(n, k):\n",
    "            return 0 if n == 1 else (helper(n - 1, k) + k) % n\n",
    "        return helper(n, k) + 1\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheWinner(self, n: int, k: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(2, n+1):\n",
    "            ans = (ans+k)%i\n",
    "        return ans+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheWinner(self, n: int, k: int) -> int:\n",
    "        # 约瑟夫环(n,k)问题 (1,k)->0 (2,k)->(k-1)%n\n",
    "        res = 0\n",
    "        for i in range(2, n+1):\n",
    "            res = (res + k)%i \n",
    "        return res + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheWinner(self, n: int, k: int) -> int:\n",
    "        nums = [x for x in range(1, n + 1)]\n",
    "        index = 0\n",
    "        while len(nums) > 1:\n",
    "            index = (index + k - 1) % len(nums)\n",
    "            nums.pop(index)\n",
    "        return nums[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findTheWinner(self, n: int, k: int) -> int:\r\n",
    "        # def josephus(n, k):\r\n",
    "        #     if n == 1:\r\n",
    "        #         return(0)\r\n",
    "        #     else:\r\n",
    "        #         return((josephus(n - 1, k) + k) % n)\r\n",
    "        # return(josephus(n, k) + 1)\r\n",
    "        # if n == 1:\r\n",
    "        #     return(1)\r\n",
    "        # else:\r\n",
    "        #     return((self.findTheWinner(n - 1, k) + k - 1) % n + 1)\r\n",
    "        ans = 0\r\n",
    "        for i in range(n - 1):\r\n",
    "            ans = (ans + k) % (i + 2)\r\n",
    "        return(ans + 1)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheWinner(self, n: int, k: int) -> int:\n",
    "        return 1 if n == 1 else (k + self.findTheWinner(n - 1, k) - 1) % n + 1\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
